package leetcode101.mathematical_problem;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code2
 * @Description 204. 计数质数
 * 给定一个数字 n，求小于 n 的质数的个数。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-24 10:09
 */
public class Code2 {
    public static void main(String[] args) {
        System.out.println(countPrimes(2));
    }

    public static int countPrimes(int n) {
        int count = n - 2; // 除去 n 和 1
        boolean[] check = new boolean[n];
        for (int i = 2; i < n; i++) {
            for (int j = 2 * i; j < n; j += i) {
                if (!check[j]) {
                    check[j] = true;
                    count--;
                }
            }
        }
        return count;
    }
}
/*
埃拉托斯特尼筛法是判断一个数字是不是质数的好方法
从 1 到 n 遍历，假设当前遍历到 m 则把所有小于 n 的 且是 m 的倍数标记为合数
 */